package com.zwy.leetcode;

import java.util.*;

public class Day05Test {
    /**
     * 最长回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        List<String> list=new ArrayList<String>();
        if(s.length()==0)return "";
        if(s.length()==1)return s;
        int start=0;
        int end=s.length()-1;
        int start0=start;
        int end0=end;

        while(start0!=s.length()-1||end0!=1){
            if(s.charAt(start0)==s.charAt(end0)){
                if(start0==end0-1||start0==end0-2){
                    list.add( s.substring(start, end+1));
                    start++;
                    start0=start;
                    end=s.length()-1;
                    end0=end;
                    continue;
                }
                start0++;
                end0--;
            }
            else{
                end--;
                end0=end;
                start0=start;
            }
            if(end==start){
                start++;
                start0=start;
                end=s.length()-1;
                end0=end;
            }
            if(end<start)break;

        }
        int max=0;
        String t=s.substring(0,1);
        for (String s1 : list) {
            if(s1.length()>max){
                max=s1.length();
                t=s1;
            }

        }
        return t;
    }

    /**
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int index=0;
        int length=nums1.length+nums2.length;
        int nums1Index=0;
        int nums2Index=0;
        Double target=length%2==0?length*1.0/2:length/2+1;
        while(index!=target){
            if(nums1[nums1Index]<nums2[nums1Index]){
                nums2Index++;
                index=nums1Index+nums2Index-1;
            }else{
                nums1Index++;
                nums2Index++;
                index=nums1Index+nums2Index;
            }
        }
        return 1.0;
    }


    /**
     *全排列
     * @param nums
     * @return
     */
    List<List<Integer>>res=new LinkedList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        fun(nums, track);
        return res;

    }
    public void fun(int []nums,LinkedList<Integer> list){
        // 触发结束条件
        if (list.size() == nums.length) {
            res.add(new LinkedList(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i]))
                continue;
            // 做选择
            list.add(nums[i]);
            // 进入下一层决策树
            fun(nums, list);
            // 取消选择
            list.removeLast();
        }
    }

    /**
     * N 皇后
     * @param n
     * @return
     */
    List<List<String>> res0 = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res0;
    }
    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            res0.add(Array2List(chessboard));
            return;
        }

        for (int col = 0;col < n; ++col) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row+1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }
    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i=0; i<n; ++i) {
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    /**
     * 斐波那契数
     * @param n
     * @return
     */
    public int fib(int n) {
        if(n==0)return 0;
        int []dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for (int i = 2; i <=n ; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    /**
     * 第 N 个泰波那契数
     * @param n
     * @return
     */
    public int tribonacci(int n) {
        if(n==0)return 0;
        if(n==1||n==2)return 1;
        int []dp=new int[n+1];
        dp[0] = 0; dp[1] = 1; dp[2] = 1;
        for (int i = 3; i <=n; i++) {
         dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
        }
        return dp[n];
    }

    /**
     * 使用最小花费爬楼梯
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        if(cost.length<2)return 0;
        int []dp=new int[cost.length];
        dp[0]=0;
        dp[1]=0;
        for (int i = 2; i < dp.length; i++) {
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return  dp[dp.length-2]+cost[dp.length-2]>dp[dp.length-1]+cost[dp.length-1]?dp[dp.length-1]+cost[dp.length-1]:dp[dp.length-2]+cost[dp.length-2];
    }

    /**
     * 打家劫舍 II
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0 || nums == null) return 0;
        if (len == 1) return nums[0];
        // 分两种情况，选第一个和不选第一个，选取两种情况下的最大值
        int[] dp0 = new int[len];
        int[] dp1 = new int[len];
        // 第一种情况，选第一个，不选第二个，以倒数第二个的金额
        // 第二种情况，选第二个，不选第一个，以最后一个金额
        dp0[0] = dp0[1] = nums[0];
        dp1[1] = nums[1];
        for (int i = 2; i < len; i++) {
            dp0[i] = Math.max(dp0[i - 1], dp0[i - 2] + nums[i]);
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }
        return Math.max(dp0[len - 2], dp1[len - 1]);
    }



    public static void main(String[] args) {
      int []arr={ 2,3,1,1,4};
        Day05Test test=new Day05Test();
//         test.jump(arr);
    }



}
